package algorithms

import (
	"Algorithms/util"
	"fmt"
	"math"
	"sort"
)

var num = 0

//8皇后问题，低配数独
var result = [8]int{} //全局或成员变量,下标表示行,值表示queen存储在哪一列
func cal8queens(row int) { // 调用方式：cal8queens(0);
	if row == 8 {
		num++
		fmt.Println("第", num, "个结果：") /// 8个棋子都放置好了，打印结果
		printQueens(result)
		return // 8行棋子都放好了，已经没法再往下递归了，所以就return
	}
	for column := 0; column < 8; column++ { // 每一行都有8种放法
		if isOk(row, column) { // 有些放法不满足要求，剪枝
			result[row] = column // 第row行的棋子放到了column列
			cal8queens(row + 1)  // 考察下一行
		}
	}
}
func isOk(row, column int) bool { //判断row行column列放置是否合适
	var leftup, rightup = column - 1, column + 1
	for i := row - 1; i >= 0; i-- { // 逐行往上考察每一行
		if result[i] == column {
			return false
		}                // 第i行的column列有棋子吗？
		if leftup >= 0 { // 考察左上对角线：第i行leftup列有棋子吗？
			if result[i] == leftup {
				return false
			}
		}
		if rightup < 8 { // 考察右上对角线：第i行rightup列有棋子吗？
			if result[i] == rightup {
				return false
			}
		}
		leftup--
		rightup++
	}
	return true
}
func printQueens(result [8]int) { // 打印出一个二维矩阵
	for row := 0; row < 8; row++ {
		for column := 0; column < 8; column++ {
			if result[row] == column {
				fmt.Print("Q ")
			} else {
				fmt.Print("* ")
			}
		}
		fmt.Println()
	}
	fmt.Println("---------------")
}

//0-1背包问题：有一个背包，背包总的承载重量是Wkg。现在我们有n个物品，每个物品的重量不等，并且不可分割。
//我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
var maxW = util.INT_MIN //存储背包中物品总重量的最大值
// cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
// w背包重量；items表示每个物品的重量；
// 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
// f(0, 0,100, a)
func f(i, cw, w int, items []int) {
	//剪枝
	if cw == w || i == len(items) { // cw==w表示装满了;i==n表示已经考察完所有的物品
		if cw > maxW {
			maxW = cw
		}
		return
	}
	//选择不装
	f(i+1, cw, w, items)
	//选择装
	if cw+items[i] <= w { // 已经超过可以背包承受的重量的时候，就不要再装了
		f(i+1, cw+items[i], w, items)
	}
}

//正则表达式，*匹配多个，？匹配01个
type Pattern struct {
	matched bool
	pattern string // 正则表达式
	plen    int    // 正则表达式长度
}

func MakePatter(pattern string) *Pattern {
	return &Pattern{
		matched: false,
		pattern: pattern,
		plen:    len(pattern),
	}
}
func (p *Pattern) Match(text string) bool { // 文本串及长度
	p.matched = false
	p.rmatch(0, 0, text)
	return p.matched
}

//ti是字符串text，pj是模式串
func (p *Pattern) rmatch(ti, pj int, text string) {
	if p.matched {
		return // 如果已经匹配了，就不要继续递归了
	}
	if pj == p.plen { // 正则表达式到结尾了
		if ti == len(text) { // 文本串也到结尾了
			p.matched = true
		}
		return
	}
	if p.pattern[pj] == '*' { // *匹配任意个字符
		for k := 0; k <= len(text)-ti; k++ {
			p.rmatch(ti+k, pj+1, text)
		}
	} else if p.pattern[pj] == '?' { // ?匹配0个或者1个字符
		//匹配0个
		p.rmatch(ti, pj+1, text)
		//匹配1个
		p.rmatch(ti+1, pj+1, text)
	} else if ti < len(text) && p.pattern[pj] == text[ti] { // 纯字符匹配才行
		p.rmatch(ti+1, pj+1, text)
	}
}

//89. 格雷编码
func grayCode(n int) []int {
	visited := make([]bool, 1<<n)
	res := make([]int, 0)
	dfs(0, n, &res, visited)
	return res
}

func isGray(a, b int) bool {
	var diff int
	if a > b {
		diff = a - b
	} else {
		diff = b - a
	}
	if diff&(diff-1) == 0 {
		return true
	}
	return false
}

func dfs(cur, n int, res *[]int, visited []bool) bool {
	*res = append(*res, cur)
	visited[cur] = true
	if len(*res) == 1<<n {
		if isGray((*res)[len(*res)-1], (*res)[0]) {
			return true
		}
		return false
	}

	//每位都改变一次
	for i := 0; i < n; i++ {
		next := cur ^ (1 << i)
		//只有符合才返回
		if !visited[next] && dfs(next, n, res, visited) {
			return true
		}
	}
	//这个弄完了，返回上次的时候需要把这次访问记录删除
	visited[cur] = false
	return false
}

var (
	res     [][]int
	visited [][]int
)

//46. 全排列
func permute(nums []int) [][]int {
	res = [][]int{}
	permuteRecuresion(nums, 0)
	return res
}
func permuteRecuresion(nums []int, n int) {
	if n == len(nums) {
		tmp := make([]int, n)
		copy(tmp, nums)
		res = append(res, tmp)
		return
	}
	for i := n; i < len(nums); i++ {
		nums[n], nums[i] = nums[i], nums[n]
		permuteRecuresion(nums, n+1)
		nums[n], nums[i] = nums[i], nums[n]
	}
}

//47. 全排列 II
func permuteUnique(nums []int) [][]int {
	sort.Ints(nums)
	res = [][]int{}
	visited = make([][]int, len(nums))
	for i := 0; i < len(visited); i++ {
		visited[i] = []int{}
	}
	permuteUniqueRecuresion(nums, 0)
	return res
}
func permuteUniqueRecuresion(nums []int, n int) {
	if n == len(nums) {
		tmp := make([]int, n)
		copy(tmp, nums)
		res = append(res, tmp)
		return
	}
	for i := n; i < len(nums); i++ {
		if check(visited[n], nums[i]) {
			continue
		} else {
			visited[n] = append(visited[n], nums[i])
			nums[n], nums[i] = nums[i], nums[n]
			permuteUniqueRecuresion(nums, n+1)
			nums[n], nums[i] = nums[i], nums[n]

		}
	}
	//这个位置已经遍历完了，不要影响其他的（前面固定遍历时可能会涉及到之后的visited）
	visited[n] = []int{}
}

func check(visited []int, num int) bool {
	for _, k := range visited {
		if k == num {
			return true
		}
	}
	return false
}

//寻找最小路径，回溯，从(0,0)到(n-1,n-1)
func minDistBT(w [][]int) int {
	min := math.MaxInt8
	m := len(w)
	n := len(w[0])
	var f func(i, j, dist int)
	f = func(i, j, dist int) {
		if i == m-1 && j == n-1 {
			dist += w[i][j]
			if min > dist {
				min = dist
			}
			return
		}
		if i < m-1 {
			f(i+1, j, dist+w[i][j])
		}
		if j < n-1 {
			f(i, j+1, dist+w[i][j])
		}
	}
	f(0, 0, 0)
	return min
}

//39. 组合总和,回溯法
func combinationSum(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	res := make([][]int, 0)
	var f func([]int, int, int)
	f = func(tmp []int, target, index int) {
		for i := index; i < len(candidates); i++ {
			if target == candidates[i] {
				add := make([]int, len(tmp)+1)
				//这里用到深复制，golang在内存不足了，会对res里面的tmp进行享元优化，修改tmp会改动整个结果集
				copy(add, append(tmp, candidates[i]))
				res = append(res, add)
				return
			} else if candidates[i] < target {
				f(append(tmp, candidates[i]), target-candidates[i], i)
			} else {
				return
			}
		}
	}
	tmp := make([]int, 0)
	f(tmp, target, 0)
	return res
}

//40. 组合总和 II，只能使用一次
func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	res := make([][]int, 0)
	n := len(candidates)
	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, candidates[n-1]+1)
	}
	var f func([]int, int, int)
	f = func(tmp []int, target, index int) {
		for i := index; i < n; i++ {
			if visited[index][candidates[i]] {
				continue
			}
			visited[index][candidates[i]] = true
			if target == candidates[i] {
				add := make([]int, len(tmp)+1)
				//这里用到深复制，golang在内存不足了，会对res里面的tmp进行享元优化，修改tmp会改动整个结果集
				copy(add, append(tmp, candidates[i]))
				res = append(res, add)
				break
			} else if candidates[i] < target {
				f(append(tmp, candidates[i]), target-candidates[i], i+1)
				//去重，不能保证tmp为空时候重复进入
				if i+1 < n && candidates[i] == candidates[i+1] {
					i++
				}
			} else {
				break
			}
		}
		if index < n {
			for i := range visited[index] {
				visited[index][i] = false
			}
		}
	}
	tmp := make([]int, 0)
	f(tmp, target, 0)
	return res
}

//51. N 皇后
func solveNQueens(n int) [][]string {
	//准备功罪
	res := [][]string{}
	str := ""
	for i := 0; i < n; i++ {
		str += "*"
	}
	temp := make([]int, n)
	bs := make([]byte, n)
	for i := range bs {
		bs[i] = '.'
	}

	var f func(int)
	formatString := func(arr []int) []string {
		strs := []string{}
		for row := 0; row < n; row++ {
			colum := arr[row]
			bs[colum] = 'Q'
			strs = append(strs, string(bs))
			bs[colum] = '.'
		}
		return strs
	}
	check := func(row, column int) bool {
		left, right := column, column
		for i := row - 1; i >= 0; i-- {
			right++
			left--
			if temp[i] == column {
				return false
			}
			if left >= 0 && temp[i] == left {
				return false
			}
			if right < n && temp[i] == right {
				return false
			}
		}
		return true
	}
	f = func(row int) {
		if row == n {
			res = append(res, formatString(temp))
			return
		}
		for column := 0; column < n; column++ {
			if check(row, column) {
				temp[row] = column
				f(row + 1)
			}
		}
	}
	f(0)
	return res
}

func totalNQueens(n int) int {
	//准备功罪
	temp := make([]int, n)
	var f func(int)
	sum := 0
	check := func(row, column int) bool {
		left, right := column, column
		for i := row - 1; i >= 0; i-- {
			right++
			left--
			if temp[i] == column {
				return false
			}
			if left >= 0 && temp[i] == left {
				return false
			}
			if right < n && temp[i] == right {
				return false
			}
		}
		return true
	}
	f = func(row int) {
		if row == n {
			sum++
			return
		}
		for column := 0; column < n; column++ {
			if check(row, column) {
				temp[row] = column
				f(row + 1)
			}
		}
	}
	f(0)
	return sum
}

//10. 正则表达式匹配
func isMatch(s string, p string) bool {
	var f func(si, pi int)
	ans := false
	f = func(si, pi int) {
		if ans {
			return
		}
		if pi == len(p) {
			if si == len(s) {
				ans = true
			}
			return
		}
		if pi+1 < len(p) && p[pi+1] == '*' {
			for k := 0; k <= len(s)-si; k++ {
				if p[pi] != '.' {
					//先看看si-sk能否匹配多个pi
					for i := 0; i < k; i++ {
						if s[si+i] != p[pi] {
							return
						}
					}
				}
				f(si+k, pi+2)
			}
		} else if p[pi] == '.' {
			f(si+1, pi+1)
		} else if si < len(s) && p[pi] == s[si] {
			f(si+1, pi+1)
		}
	}
	f(0, 0)
	return ans
}

//79. 单词搜索
func exist(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	visited := make([][]bool, m)
	for i := range visited {
		visited[i] = make([]bool, n)
	}
	var f func(i, j, wordIndex int) bool
	f = func(i, j, wordIndex int) bool {
		if wordIndex == len(word) {
			return true
		}
		if i == m || i < 0 || j == n || j < 0 || visited[i][j] {
			return false
		}

		res := false
		if board[i][j] == word[wordIndex] {
			visited[i][j] = true
			res = f(i+1, j, wordIndex+1) || f(i, j+1, wordIndex+1) || f(i-1, j, wordIndex+1) || f(i, j-1, wordIndex+1)
			visited[i][j] = false
		}
		return res
	}
	for i := range board {
		for j := range board[i] {
			if f(i, j, 0) {
				return true
			}
		}
	}
	return false
}

func findTargetSumWays(nums []int, target int) int {
	var f func(int,int,int)
	ans:=0
	f= func(i int,sign int,sum int) {
		temp:=sum+sign*nums[i]
		if i==len(nums)-1{
			if temp==target{
				ans++
			}
			return
		}
		f(i+1,1,temp)
		f(i+1,-1,temp)
	}
	f(0,1,0)
	f(0,-1,0)
	return ans
}